# 491.递增子序列
# 给你一个整数数组nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素 。你可以按任意顺序返回答案。
# 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
#
# 示例1：
# 输入：nums = [4, 6, 7, 7]
# 输出：[[4, 6], [4, 6, 7], [4, 6, 7, 7], [4, 7], [4, 7, 7], [6, 7], [6, 7, 7], [7, 7]]
#
# 示例2：
# 输入：nums = [4, 4, 3, 2, 1]
# 输出：[[4, 4]]


class Solution:
    def findSubsequences(self, nums: [int]):
        # 树层上去重，树枝上不去重
        res = []
        path = []
        def backtracking(nums,startindex): # 用startindex来避免重复
            # 子集类问题可以不写终止条件
            if len(path) > 1:
                res.append(path[:])
            use = [] # 是否使用过
            for i in range(startindex,len(nums)):
                # 加入数据条件有三，1.当前数比path最后一个数大，2.path不为空，3.未出现在use里
                if (path and nums[i] < path[-1] )or nums[i] in use:
                        continue
                path.append(nums[i])
                use.append(nums[i])
                backtracking(nums, i+1)
                path.pop()
        backtracking(nums,0)
        return res


if __name__ == '__main__':
    nums = [4,6,7,7]
    tmp = Solution()
    res = tmp.findSubsequences(nums)
    res.sort()
    print(res)